#ifndef GUARD_QUICK_SORT_H
#define GUARD_QUICK_SORT_H
#include "misc.h"
#include <stdio.h>

typedef struct _node{
    int low;
    int high;
}Node;
void Swap_q(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int *a, int begin, int end)
{
    int key_index = (end + begin) / 2;
    int key = a[key_index];
    int i = begin - 1;
    int j = begin;
    int temp = 0;
    for(j; j < end; ++j)
    {
        if((j != key_index) && (a[j] <= key))
        {
            ++i;
            //Swap_q(&a[i], &a[j]);
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    //Swap_q(&a[i + 1], &a[end]);
    temp = a[i+1];
    a[i+1] = a[key_index];
    a[key_index] = temp;
    return i + 1;
}

void quick_sort_rec(int *a, int begin, int end)
{
    int split = 0;
    int i = 0;
    if (begin < end)
    {
        split = partition(a, begin, end);
        quick_sort_rec(a, begin, split - 1);
        quick_sort_rec(a, split + 1, end);
    }
}
int partition_1(int *a, int begin, int end)
{
    int key = 0;
    int i = 0;
    int j = 0;
    int temp = 0;
    for(i = begin; i <= end; ++i)
    {
        key += a[i];
    }
    key = key / (end - begin + 1);

    i = begin - 1;
    for(j = begin; j < end; ++j)
    {
        if((a[j] <= key))
        {
            ++i;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    return i + 1;
}
void quick_sort(int *a, int len)
{
    Node stack[100] = {0};
    int low = 0;
    int high = len - 1;
    int top = 0;
    int pos = 0;

    stack[top].low = 0;
    stack[top].high = len - 1;

    while(top >= 0)
    {
        low = stack[top].low;
        high = stack[top].high;
        --top;
        if(low < high)
        {
            pos = partition_1(a, low, high);
            ++top;
            stack[top].low = low;
            stack[top].high = pos - 1;
            ++top;
            stack[top].low = pos + 1;
            stack[top].high = high;
        }
    }
}
#endif